/*
 * TurboReverseFactor.cpp
 *
 *  Created on: 01-09-2013
 *      Author: Krzychu
 */

#include "TurboReverseFactor.h"

#include "../Structures/Config.h"
#include "../Structures/SuffixAutomaton.h"

#define ASIZE 255

TurboReverseFactor::TurboReverseFactor()
{

}

TurboReverseFactor::~TurboReverseFactor()
{

}

std::string TurboReverseFactor::getName()
{
	return "Turbo Reverse Factor";
}

searchResult TurboReverseFactor::execute(std::string text, std::string pattern)
{
	searchResult result;
	result.iterationsTaken = 0;

	int textSize = text.size();
	int patternSize = pattern.size();

	int period, i, j, shift, u, periodOfU, disp, init, state, mu;

	/* Preprocessing */

	std::string patternR = reverse(pattern);
	SuffixAutomaton* aut = new SuffixAutomaton(2 * (patternSize + 2), 2 * (patternSize + 2) * ASIZE);
	buildSuffixAutomaton(patternR, aut);

	init = aut->getInitial();
	int* mpNext = preMp(pattern);
	period = patternSize - mpNext[patternSize];
	i = 0;
	shift = patternSize;

	/* Searching */
	j = 0;
	while (j <= textSize - patternSize)
	{
		result.iterationsTaken++;

		i = patternSize - 1;
		state = init;
		u = patternSize - 1 - shift;
		periodOfU = (shift != patternSize ? patternSize - shift - mpNext[patternSize - shift] : 0);
		shift = patternSize;
		disp = 0;
		while (i > u && aut->getTarget(state, text[i + j]) != aut->getUndefined())
		{
			disp += aut->getShift(state, text[i + j]);
			state = aut->getTarget(state, text[i + j]);
			if (aut->isTerminal(state))
			{
				shift = i;
			}
			--i;
		}
		if (i <= u)
		{
			if (disp == 0)
			{
				result.positionsFound.push_back(j);
				if (Config::getInstance()->getFindOneOccurence())
				{
					return result;
				}

				shift = period;
			}
			else
			{
				mu = (u + 1) / 2;
				if (periodOfU <= mu)
				{
					u -= periodOfU;
					while (i > u && aut->getTarget(state, text[i + j]) != aut->getUndefined())
					{
						disp += aut->getShift(state, text[i + j]);
						state = aut->getTarget(state, text[i + j]);
						if (aut->isTerminal(state))
						{
							shift = i;
						}
						--i;
					}
					if (i <= u)
					{
						shift = disp;
					}
				}
				else
				{
					u = u - mu - 1;
					while (i > u && aut->getTarget(state, text[i + j]) != aut->getUndefined())
					{
						disp += aut->getShift(state, text[i + j]);
						state = aut->getTarget(state, text[i + j]);
						if (aut->isTerminal(state))
						{
							shift = i;
						}
						--i;
					}
				}
			}
		}
		j += shift;
	}

	return result;
}

